package exam.microsoft.second.task3;

class Solution {
    public int solution(int[] A, int[] B) {
        for (int i=0; i<A.length; ++i)
            A[i] = Math.max(A[i], B[i]);
        return firstMissingPositive(A);
    }

    public int firstMissingPositive(int[] nums) {
        for (int i=0; i<nums.length; ++i) {
            if (nums[i] >= 1 && nums[i] <= nums.length) {
                if (nums[i] == i+1)
                    continue;
                int k = nums[i];
                while (true) {
                    int j = k - 1;
                    if (nums[j] == j+1)
                        break;
                    if (nums[j] <= 0 || nums[j] > nums.length) {
                        nums[j] = k;
                        break;
                    }
                    int t = nums[j];
                    nums[j] = k;
                    k = t;
                }
            }

        }
        for (int i=0; i<nums.length; ++i) {
            if (nums[i] != i+1)
                return i + 1;
        }
        return nums.length + 1;
    }
}
